package com.data.basic.chapter11;

import java.util.Random;

/** 测试并查集性能
 * @author wang on 2018/7/3.
 */
public class Main {

    private static double testUF(UF uf ,int m){
        int size = uf.getSize();
        Random random = new Random();
        long startTime = System.nanoTime();
        for (int i=0;i<m;i++){
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.unionElements(a,b);
        }
        for (int i=0;i<m;i++){
            int a = random.nextInt(size);
            int b = random.nextInt(size);
            uf.isConnected(a,b);
        }



        long endTime = System.nanoTime();

        return (endTime-startTime)/1000000000.0;

    }

    public static void main(String[] args) {
        int size = 100000;
        int m  = 100000;
        UnionFind1 unionFind1 = new UnionFind1(size);
        UnionFind2 unionFind2 = new UnionFind2(size);
        UnionFind3 unionFind3 = new UnionFind3(size);
        UnionFind4 unionFind4 = new UnionFind4(size);
        UnionFind5 unionFind5 = new UnionFind5(size);
        UnionFind6 unionFind6 = new UnionFind6(size);
        System.out.println("数组结构的UF==>"+testUF(unionFind1,m)+"s");
        System.out.println("森林结构的UF==>"+testUF(unionFind2,m)+"s");
        System.out.println("size优化的森林结构的UF==>"+testUF(unionFind3,m)+"s");
        System.out.println("rank优化的森林结构的UF==>"+testUF(unionFind4,m)+"s");
        System.out.println("路径压缩+rank优化的森林结构的UF==>"+testUF(unionFind5,m)+"s");
        System.out.println("两层+路径压缩+rank优化的森林结构的UF==>"+testUF(unionFind6,m)+"s");

    }
}
